package easy;

public class _136_SingleNumber {
    //元素增加时时间消耗非线性增加，超时
    public int singleNumber0(int[] nums) {
        int length = nums.length;
        for(int i=0;i<length;i++){
            boolean flag = false;
            for(int j=0;j<length;j++){
                if(j!=i){
                    if(nums[i]==nums[j]){
                        flag = true;
                        break;
                    }
                }
            }
            if(!flag){
                return nums[i];
            }
        }
        return 0;
    }
    //使用额外的boolean空间保存单双值，通过测试
    public int singleNumber1(int[] nums) {
        int length = nums.length;
        boolean[] flags = new boolean[length];
        for(int i=0;i<length;i++){
//            flags[i] = true;
            if(!flags[i]){
                boolean notSingle = false;
                for(int j=i+1;j<length;j++){
                    if(!flags[j]){
                        if(nums[i]==nums[j]){
                            flags[j] = true;
                            notSingle = true;
                            break;
                        }
                    }
                }
                if(!notSingle){
                    return nums[i];
                }
            }
        }
        return 0;
    }

    //方法二：使用异或符号
    public int singleNumber(int[] nums) {
        if(nums==null) return 0;
        int val = nums[0];
        int length = nums.length;
        for(int i=1;i<length;i++){
            val ^=nums[i];
        }
        return val;
    }
}
